#include<iostream>
#include<vector>
using namespace std;

// 累计排列的个数
int cnt = 0;

// 输出一个解
void disp(vector<int> &a)
{
	printf(" %2d: (", ++cnt);
	for (int i=0; i<a.size()-1; i++)
		printf("%d,", a[i]);
	printf("%d)", a.back());
	printf("\n");
}

// 递归算法
void dfs(vector<int>& a, int i)
{
	// 求a的长度
	int n = a.size();
	
	// 打印解
	if (i >= n-1)
		disp(a);
	else
	{	for (int j=i; j<n; j++)
		{
			// 交换a[i]与a[j]
			swap(a[i], a[j]);
			
			// 递归
			dfs(a, i+1);
			
			// 交换a[i]与a[j]：恢复
			swap(a[i], a[j]);
		}
	}
}

// 求a的全排列
void perm(vector<int>& a)
{
	dfs(a, 0);
}

int main()
{
	// 初始化数组
	vector<int> a = {1, 2, 3};
	
	// 求全排列
	printf("a的全排列\n");
	perm(a);
	return 0;
}
